/**
 * @a https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 */

#include "common.h"
class Solution
{
private:
    vector<int> _tmp;

public:
    int reversePairs(vector<int> &record)
    {
        _tmp.resize(record.size());
        _tmp = record;
        return _reversePairs(record.begin(), record.end());
    }
    int _reversePairs(vector<int>::iterator begin, vector<int>::iterator end)
    {
        int sz = end - begin;
        int ret = 0;
        if (sz <= 1)
            return 0;

        // auto mid = begin + (sz / 2);
        auto mid = begin + (sz >> 1);
        ret += _reversePairs(begin, mid);
        ret += _reversePairs(mid, end);

        auto curr1 = begin, curr2 = mid;
        int i = 0;

        // while(curr1 < mid && curr2 < end)
        // {
        //     if(*curr1 )
        // }
        while (curr1 < mid && curr2 < end)
        {
            if(*curr1 <= *curr2)
            {
                _tmp[i++] = *curr1++;
            }
            else{
                ret += mid - curr1;
                _tmp[i++] = *curr2++;   
            }
        }
        while (curr1 < mid)
        {
            _tmp[i++] = *curr1++;
        }
        while (curr2 < end)
        {
            _tmp[i++] = *curr2++;
        }

        for(int j = 0; j < sz; ++j){
            *begin++ = _tmp[j];
        }
        return ret;
    }
};



class Solution
{
private:
    vector<int> _tmp;

public:
    int reversePairs(vector<int> &record)
    {
        _tmp.resize(record.size());
        _tmp = record;
        return _reversePairs(record.begin(), record.end());
    }
    int _reversePairs(vector<int>::iterator begin, vector<int>::iterator end)
    {
        int sz = end - begin;
        int ret = 0;
        if (sz <= 1)
            return 0;

        auto mid = begin + (sz / 2);

        ret += _reversePairs(begin, mid);
        ret += _reversePairs(mid, end);

        auto curr1 = begin, curr2 = mid;
        int i = 0;

        while (curr1 < mid && curr2 < end)
        {
            if(*curr1 <= *curr2)
            {
                _tmp[i++] = *curr1++;
            }
            else{
                ret += mid - curr1;
                _tmp[i++] = *curr2++;   
            }
        }
        while (curr1 < mid)
        {
            _tmp[i++] = *curr1++;
        }
        while (curr2 < end)
        {
            _tmp[i++] = *curr2++;
        }

        copy(_tmp.begin(), _tmp.begin() + sz, begin);
        // for(int j = 0; j < sz; ++j){
        //     *begin++ = _tmp[j];
        // }
        return ret;
    }
};